package com.future;

/**
 * Description:
 * 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
 * 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
 * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
 * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-common-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2021/12/22 09:28
 */
public class Solution_longestCommonSubsequence_1143 {

    public static void main(String[] args) {
        String text1 = "abcde", text2 = "ace";
        System.out.println(longestCommonSubsequence1(text1, text2));
        System.out.println(longestCommonSubsequence2(text1, text2));
    }

    /**
     * 暴力方法，超时
     *
     * @param s1
     * @param s2
     * @return
     */
    public static int longestCommonSubsequence1(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
            return 0;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        // 尝试
        return process1(str1, str2, str1.length - 1, str2.length - 1);
    }

    // str1[0...i]和str2[0...j]，这个范围上最长公共子序列长度是多少？
    // 可能性分类：
    // a) 最长公共子序列，既不以str1[i]字符结尾、也不以str2[j]字符结尾
    // 比如: str1[0..5] = "1a234b", str2[0..7] = "cd12e34f"
    // 其中最长公共子序列为"1234"
    // 可以看到，这个最长公共子序列根本和str1[i]字符、str2[j]字符没有任何关系
    // a)的可能性下，最长公共子序列总长度 =
    // str1[0...i-1]与str2[0...j-1]的最长公共子序列长度(后续递归)
    // ======================================================
    // b) 最长公共子序列，以str1[i]字符结尾、不以str2[j]字符结尾
    // 比如: str1[0..5] = "1a23b4", str2[0..7] = "cd12e34f"
    // 其中最长公共子序列为"1234"
    // 可以看到，这个最长公共子序列以str1[i]字符结尾，但是不以str2[j]字符结尾
    // b)的可能性下，最长公共子序列总长度 =
    // str1[0...i]与str2[0...j-1]的最长公共子序列长度(后续递归)
    // ======================================================
    // c) 最长公共子序列，不以str1[i]字符结尾、以str2[j]字符结尾
    // 比如: str1[0..5] = "1a234b", str2[0..7] = "cd12e3f4"
    // 其中最长公共子序列为"1234"
    // 可以看到，这个最长公共子序列不以str1[i]字符结尾，以str2[j]字符结尾
    // c)的可能性下，最长公共子序列总长度 =
    // str1[0...i-1]与str2[0...j]的最长公共子序列长度(后续递归)
    // ======================================================
    // d) 最长公共子序列，同时以str1[i]字符和str2[j]字符结尾
    // 比如: str1[0..5] = "1a23b4", str2[0..7] = "cd12ef34"
    // 其中最长公共子序列为"1234"
    // 可以看到这个公共子序列的结尾是'4'，同时以str1[5]字符和str2[7]字符结尾
    // 同时可以看到，可能性d)存在的条件，一定是在str1[i] == str2[j]的情况下，才成立的
    // d)的可能性下，最长公共子序列总长度 =
    // str1[0...i-1]与str2[0...j-1]的最长公共子序列长度(后续递归) + 1(共同的结尾)
    // ======================================================
    // 综上，四种情况已经穷尽了所有可能性。四种情况中取最大即可
    // 其中b)、c)一定参与最大值的比较，
    // 当str1[i] == str2[j]时，a)一定比d)小，所以d)参与
    // 当str1[i] != str2[j]时，d)压根不存在，所以a)参与
    // 但是再次注意了！
    // a)是：str1[0...i-1]与str2[0...j-1]的最长公共子序列长度
    // b)是：str1[0...i]与str2[0...j-1]的最长公共子序列长度
    // c)是：str1[0...i-1]与str2[0...j]的最长公共子序列长度
    // a)中str1的范围 < b)中str1的范围，a)中str2的范围 == b)中str2的范围
    // 所以a)不用求也知道，它比不过b)啊，因为有一个样本的范围比b)小啊！
    // a)中str1的范围 == c)中str1的范围，a)中str2的范围 < c)中str2的范围
    // 所以a)不用求也知道，它比不过c)啊，因为有一个样本的范围比c)小啊！
    // 至此，可以知道，a)就是个垃圾，有它没它，都不影响最大值的决策
    // 所以，当str1[i] == str2[j]时，b)、c)、d)中选出最大值
    // 当str1[i] != str2[j]时，b)、c)中选出最大值
    public static int process1(char[] str1, char[] str2, int i, int j) {
        if (i == 0 && j == 0) {
            // str1[0..0]和str2[0..0]，都只剩一个字符了
            // 那如果字符相等，公共子序列长度就是1，不相等就是0
            // 这显而易见
            return str1[i] == str2[j] ? 1 : 0;
        } else if (i == 0) {
            // 这里的情况为：
            // str1[0...0]和str2[0...j]，str1只剩1个字符了，但是str2不只一个字符
            // 因为str1只剩一个字符了，所以str1[0...0]和str2[0...j]公共子序列最多长度为1
            // 如果str1[0] == str2[j]，那么此时相等已经找到了！公共子序列长度就是1，也不可能更大了
            // 如果str1[0] != str2[j]，只是此时不相等而已，
            // 那么str2[0...j-1]上有没有字符等于str1[0]呢？不知道，所以递归继续找
            if (str1[i] == str2[j]) {
                return 1;
            } else {
                return process1(str1, str2, i, j - 1);
            }
        } else if (j == 0) {
            // 和上面的else if同理
            // str1[0...i]和str2[0...0]，str2只剩1个字符了，但是str1不只一个字符
            // 因为str2只剩一个字符了，所以str1[0...i]和str2[0...0]公共子序列最多长度为1
            // 如果str1[i] == str2[0]，那么此时相等已经找到了！公共子序列长度就是1，也不可能更大了
            // 如果str1[i] != str2[0]，只是此时不相等而已，
            // 那么str1[0...i-1]上有没有字符等于str2[0]呢？不知道，所以递归继续找
            if (str1[i] == str2[j]) {
                return 1;
            } else {
                return process1(str1, str2, i - 1, j);
            }
        } else { // i != 0 && j != 0
            // 这里的情况为：
            // str1[0...i]和str2[0...i]，str1和str2都不只一个字符
            // 看函数开始之前的注释部分
            // p1就是可能性c)
            int p1 = process1(str1, str2, i - 1, j);
            // p2就是可能性b)
            int p2 = process1(str1, str2, i, j - 1);
            // p3就是可能性d)，如果可能性d)存在，即str1[i] == str2[j]，那么p3就求出来，参与pk
            // 如果可能性d)不存在，即str1[i] != str2[j]，那么让p3等于0，然后去参与pk，反正不影响
            int p3 = str1[i] == str2[j] ? (1 + process1(str1, str2, i - 1, j - 1)) : 0;
            return Math.max(p1, Math.max(p2, p3));
        }
    }

    /**
     * 动态规划
     *
     * @param text1
     * @param text2
     * @return
     */
    public static int longestCommonSubsequence2(String text1, String text2) {
        if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) {
            return 0;
        }
        char[] str1 = text1.toCharArray();
        char[] str2 = text2.toCharArray();
        int M = str1.length;
        int N = str2.length;
        int[][] dp = new int[M][N];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        for (int i = 1; i < N; i++) {
            dp[0][i] = str1[0] == str2[i] ? 1 : dp[0][i - 1];
        }
        for (int k = 1; k < M; k++) {
            dp[k][0] = str1[k] == str2[0] ? 1 : dp[k - 1][0];
        }
        for (int i = 1; i < M; i++) {
            for (int j = 1; j < N; j++) {
                int p1 = dp[i - 1][j];
                int p2 = dp[i][j - 1];
                int p3 = str1[i] == str2[j] ? (1 + dp[i - 1][j - 1]) : 0;
                dp[i][j] = Math.max(p1, Math.max(p2, p3));
            }
        }
        return dp[M - 1][N - 1];
    }


}
